package main.leetcode.clockin.April;

import java.util.Arrays;

/**
 * 面试题51.数组中的逆序对
 *
 * <p>在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
 *
 * <p>
 *
 * <p>示例 1:
 *
 * <p>输入: [7,5,6,4] 输出: 5
 *
 * <p>限制：
 *
 * <p>0 <= 数组长度 <= 50000
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class day24 {
    private int res;
    private int[] aux;

    public static void main(String[] args) {
        System.out.println(new day24().reversePairs(new int[] {7, 5, 6, 4}));
        System.out.println(new day24().reversePairs(new int[] {4, 3, 3, 1, 0}));
    }

    public int reversePairs(int[] nums) {
        res = 0;
        int n = nums.length;
        aux = new int[n];
        mergeSort(nums, 0, nums.length - 1);
        System.out.println(Arrays.toString(nums));
        return res;
    }

    private void mergeSort(int[] nums, int l, int r) {
        if (l >= r) {
            return;
        }
        int mid = l + ((r - l) >> 1);
        mergeSort(nums, l, mid);
        mergeSort(nums, mid + 1, r);
        // 已经有序
        if (nums[mid] <= nums[mid + 1]) {
            return;
        }
        merge(nums, l, mid, r);
    }

    private void merge(int[] nums, int l, int mid, int r) {
        int i = l;
        int j = mid + 1;
        System.arraycopy(nums, l, aux, l, r - l + 1);
        for (int k = l; k <= r; ++k) {
            if (i > mid) {
                nums[k] = aux[j++];
            } else if (j > r) {
                nums[k] = aux[i++];
            } else if (aux[i] <= aux[j]) {
                nums[k] = aux[i++];
            } else {
                res += mid - i + 1;
                nums[k] = aux[j++];
            }
        }
    }
}
